Вычисление наибольшего общего делителя
2025-10-04
Ознакомиться с алгоритмами вычисления наибольшего общего делителя. Реализовать их.
Реализовать на языке программирования Julia:
Целое число \(d \neq 0\) называется наибольшим общим делителем чисел \(a_1, a_2, ..., a_k\), если:
Рисунок 1: Алгоритм Евклида. Пример отработки
function binary_gcd(a::Int, b::Int)
if b <= 0 || a < b
error("error a, b, please use 0 < b <= a")
end
g = 1 #mnojitel dlya u4eta obshih 2
while a % 2 == 0 && b % 2 == 0
a /= 2
b /= 2
g *= 2
end
u = a #first num
v = b # second num
while u != 0
# udalyaem mnojiteli 2 is u
while u % 2 == 0
u /= 2
end
# udalyaem mnojiteli 2 is v
while v % 2 == 0
v /= 2
end
if u >= v
u = u - v
else
v = v - u
end
end
return g * v
endРисунок 2: Бинарный алгоритм Евклида. Пример отработки
function extended_gcd(a::Int, b::Int)
if b <= 0 || a < b
error("error a, b, please use 0 < b <= a")
end
#xa+yb=gcd
r0, r1 = a, b
x0, x1 = 1, 0
y0, y1 = 0, 1
while r1 != 0
q = div(r0, r1) #4astnoe
r_next = r0 - q * r1 #sled.ostatok
x_next = x0 - q * x1 #koeff x
y_next = y0 - q * y1 #koeff y
#sdvig
r0, r1 = r1, r_next
x0, x1 = x1, x_next
y0, y1 = y1, y_next
end
return r0, x0, y0
endРисунок 3: Расширенный алгоритм Евклида. Пример отработки
function extended_binary_gcd(a::Int, b::Int)
if b <= 0 || a < b
error("error a, b, please use 0 < b <= a")
end
g = 1 #mnojitel dlya u4eta obshih 2
u = a #first num
v = b # second num
#koeff dlya lin.predstavleniya
A = 1
B = 0
C = 0
D = 1
while u % 2 == 0 && v % 2 == 0
u /= 2
v /= 2
g *= 2
end
while u != 0
# obrabotka 4etnosti u
while u % 2 == 0
u ÷= 2 #
# obnovlyaem koeff A B
if A % 2 == 0 && B % 2 == 0
A ÷= 2 # if oba 4et - to delim na 2
B ÷= 2
else
A = (A + b) ÷ 2 # ina4e primenyam sled formulu
B = (B - a) ÷ 2
end
end
# obrabotka 4etnosti v
while v % 2 == 0
v ÷= 2 #
# obnovlyaem koeff C D
if C % 2 == 0 && D % 2 == 0
C ÷= 2 # if oba 4et - to delim na 2
D ÷= 2
else
C = (C + b) ÷ 2 # ina4e primenyam sled formulu
D = (D - a) ÷ 2
end
end
if u >= v
u = u - v #
A = A - C # obnovlyaem koeff
B = B - D
else
v = v - u #
C = C - A # obnovlyaem koeff
D = D - B
end
end
d = g * v
# koeff x y
x = C
y = D
return d, x, y
end Рисунок 4: Расширенный бинарный алгоритм Евклида. Пример отработки
В ходе лабораторной работы реализованы на языке программирования Julia: